//
// Created by liuyang on 15-9-12.
//

#ifndef GRAPH_GRAPH_H
#define GRAPH_GRAPH_H
#define MAX_VERTEX 50

#include <sstream>
#include <cstring>
#include "stack.h"
#include "queue.h"

struct List{
    List(){
        next = NULL;
        value = -1;
        site = -1;
    }
    List * next;
    int site;
    int value;
};

class Graph{
public:
    int Matrix[MAX_VERTEX][MAX_VERTEX];
    List Adj[MAX_VERTEX];
    int vertexCount;
    //Constructor
    Graph():vertexCount(0){
        for(int i = 0; i < MAX_VERTEX; i++){
            for(int j = 0; j < MAX_VERTEX; j++){
                Matrix[i][j] = 0;
            }
            Adj[i].value = -1;
            Adj[i].next = NULL;
        }
    }

    void initMatrix(int newMatrix[MAX_VERTEX][MAX_VERTEX], int newVertexCount){
        for(int i = 0; i < MAX_VERTEX; i++) {
            for (int j = 0; j < MAX_VERTEX; j++) {
                Matrix[i][j] = newMatrix[i][j];
            }
            vertexCount = newVertexCount;
        }
        buildAdj();
    }

    void buildAdj(){
        for(int i = 0; i < vertexCount; i++){
            Adj[i].site = i;
            Adj[i].value = 0;
            Adj[i].next = NULL;
        }
        for(int i = 0; i < vertexCount; i++){
            for(int j = 0; j < vertexCount; j++){
                if(Matrix[i][j] > 0){
                    List * pointer = &Adj[i];
                    while(pointer->next != NULL){
                        pointer = pointer->next;
                    }
                    pointer->next = new List;
                    pointer->next->next = NULL;
                    pointer->next->value = Matrix[i][j];
                    pointer->next->site = j;
                }
            }
        }
    }

    std::string printAdj(){
        std::stringstream stream;
        for(int i = 0; i < vertexCount; i++){
            stream << i << ":";
            List * pointer = &Adj[i];
            while(pointer != NULL){
                stream << "(value:" << pointer->value << ",site:" << pointer->site << ") --> ";
                pointer = pointer->next;
            }
            stream << "NULL" << "\n";
        }
        return stream.str();
    }

    std::string DFS_recur_in(int i, int arr[MAX_VERTEX]){
        std::stringstream ss;
        if(arr[i] == 1) return ss.str();
        ss <<"遍历: "<< "site:" << Adj[i].site << ",value:" <<Adj[i].value << std::endl;
        arr[i] = 1;
        List * pointer = Adj[i].next;
        while(pointer != NULL){
            DFS_recur_in(pointer->site, arr);
            pointer = pointer->next;
        }
        return ss.str();
    }

    std::string DFS(int i){
        std::stringstream ss;
        int arr[MAX_VERTEX] = {0};
        Stack<List *> s;
        s.push_back(&Adj[i]);
        arr[i] = 1;
        ss << "栈变化: " << Adj[i].site << "->push_back" << std::endl;
        while(!s.isEmpty()){
            List * pointer = s.pop_back();
            ss << "栈变化: " << pointer->site << "->pop_back" << std::endl;
            ss <<"遍历: "<< "site:" << pointer->site << ",value:" << pointer->value << std::endl;
            pointer = Adj[pointer->site].next;
            while(pointer != NULL) {
                if (arr[pointer->site] == 0){
                    s.push_back(pointer);
                    arr[pointer->site] = 1;
                    ss << "栈变化: " << pointer->site << "->push_back" << std::endl;
                }
                pointer = pointer->next;
            }
        }
        return ss.str();
    }

    std::string DFS_recur(int i){
        int arr[MAX_VERTEX] = {0};
        return DFS_recur_in(i, arr);
    }

    std::string BFS(int i){
        std::stringstream ss;
        int arr[MAX_VERTEX] = {0};
        Queue<List *> q;
        q.push_back(&Adj[i]);
        ss <<"队列变化: " << Adj[i].site << "->push_back" << std::endl;
        arr[MAX_VERTEX] = 1;
        while(!q.isEmpty()){
            List * pointer = q.pop_front();
            ss <<"队列变化: " << pointer->site << "->pop_front" << std::endl;
            ss <<"遍历: "<< "site:" << pointer->site << ",value:" << pointer->value << std::endl;
            pointer = Adj[pointer->site].next;
            while(pointer != NULL){
                if(arr[pointer->value] == 0){
                    q.push_back(pointer);
                    ss <<"队列变化:" << pointer->site << "->push_back" << std::endl;
                    arr[pointer->value] = 1;
                }
                pointer = pointer->next;
            }
        }
        return ss.str();
    }
};


#endif //GRAPH_GRAPH_H
